#!/usr/local/bin/python -t
# -*- coding: utf8 -*-
'''
Classes for sorted lists counting or storing in a list equal elements
and a test for them.
'''

import types

DEBUG = 0

def show(obj):
    '''Debugging tool: show everything about obj.'''
    res = 'show: %s\n' % str(obj)
    for _ii in dir(obj):
        res += '  show: %s: %s\n' % (_ii, str(getattr(obj, _ii)))
    return res

def log(msg, level=1, prefix=None):
    '''Report a warning, a notice, or a debug message.'''
    if level <= DEBUG:
        if prefix is None:
            print msg
        else:
            print prefix, msg

class SortedBundledList(list):
    '''A class of ordered (sorted in descending order) array of elements
    with equal elements bundled as a list.
    '''

    def __str__(self):
        return '%s:\n%d:[%s]' % (self.__class__.__name__, len(self), \
                            ', '.join([str(_i) for _i in self]))

    def check(self, _): #pylint: disable=R0201
        '''Does the element belong here?'''
        return True

    def find(self, element):
        '''obj.find(element) -> is_in, index

        Find a place for inserting a new element keeping the order and
        bundling equal elements. Return a tuple (boolean, index), boolean
        indicates whether equal elements exist. There should be defined
        element.cmp(par) comparing element to a list-like par.
        Initialize limits and call the actual routine.
        '''
        return self.do_find(element, 0, len(self)-1)

    def do_find(self, element, _low, _high):
        '''obj.find(element) -> is_in, index

        Find a place for inserting a new element keeping the order and
        bundling equal elements. Return a tuple (boolean, index), boolean
        indicates whether equal elements exist. There should be defined
        element.cmp(par) comparing element to a list-like par.
        Actual binary search.
        '''
        if _low > _high:
            return False, _low
        _current = _low + (_high - _low) // 2
        _cmp = element.cmp(self[_current])
        if _cmp == 0:
            return True, _current
        elif _cmp < 0:
            return self.do_find(element, _current+1, _high)
        else: # _cmp > 0:
            return self.do_find(element, _low, _current-1)

    def insert(self, element):
        '''obj.insert(element)

        Insert a new element keeping the order and bundling equal elements.
        There should be defined element.list() returning a list-like object,
        element.cmp(par) comparing element to a list-like par, and the
        list-like objects should have a function obj.append(element).
        Binary insert (via obj.find(element)).
        '''
        assert self.check(element)
        _is_in, _index = self.find(element)
        if _is_in:
            self[_index].append(element)
        else:
            list.insert(self, _index, element.list())

class Cmp(object):
    '''Abstract class with methods cmp() and list() for inhiretance.'''

    def cmp(self, value):
        '''Compare self to value, return negative, 0, or positive
        if less, equal, or greater, respectively. Value can be a list.'''

        if isinstance(value, types.ListType):
            return cmp(self, value[0])
        else:
            return cmp(self, value)

    def list(self):
        '''Make a list'''
        return [self]

# Example classes
class Float(float, Cmp):
    '''Derive a simplistic class with methods cmp() and list().'''
    pass

class Count():
    '''Define a counting class with methods cmp(), list(), and append().'''

    def __init__(self, _):
        self.count = 1

    def __str__(self):
        if self.count == 1:
            return ''
        else:
            return '(x%d)' % (self.count)

    def cmp(self, value):
        '''Compare self to value, return negative, 0, or positive
        if less, equal, or greater, respectively.'''
        return cmp(self, value)

    def list(self):
        '''This class is a list-like class.'''
        return self

    def append(self, value):
        '''Count instancies of same value.'''
        assert self == value
        self.count += 1

class Int(int, Count):
    '''Define a class counting integer instances.'''

    def __init__(self, value):
        int.__init__(self, value)
        Count.__init__(self, value)

    def __str__(self):
        return '%d%s' % (self, Count.__str__(self))

class Str(str, Count): #pylint: disable=R0904
    '''Define a class counting strings.'''

    def __init__(self, value):
        str.__init__(self, value)
        Count.__init__(self, value)

    def __str__(self):
        return '%s%s' % (str.__str__(self), Count.__str__(self))

#### Testing staff
if __name__ == "__main__":

    import sys
    import random

    def test1(array, debug=0):
        '''Test the class with a given array.'''

        if debug > 0:
            print 'Test array:', array
        _slm = SortedBundledList()
        if debug > 0:
            print 'Just created:', _slm
        for _ind in array:
            _slm.insert(_ind)
            if debug > 0:
                print 'After inserting', _ind, ':', _slm
            _sslm = sorted(_slm, reverse=True)
            assert _sslm == _slm, \
              'Not sorted after inserting %s:\n%s\n!=\n%s' % (_ind,
                                                        show(_slm), show(_sslm))

    def test(*varg):
        '''Run the tests with given or random data.
        Numerical parameters can be given in the command line for tests.
        Three least significant bits of the first parameter:
        LSB: verbose.
        LSB+1: run a test for Int().
        LSB+2: run a test for Float().
        LSB+3: run a test for Str().
        If exactly 2 parameters are given, the second is the length of a
        randomly generated test sequence.
        If more than 2 parameters are given, the second and further parameters
        are used as the test sequence (two times if both tests are run).
        No parameters is equivalent to giving two pamaters 14 32 (i.e. all
        three tests, not verbose, with sequences of 32 random numbers each,
        also used as strings for Str). This produces output only in case of
        errors.
        '''

        varg = varg[0]
        debug = 0
        length = 32
        if len(varg) > 0:
            debug = int(varg[0])
        if len(varg) == 2:
            length = int(varg[1])
        if debug & 2:
            if len(varg) > 2:
                arr = [Int(_i) for _i in varg[1:]]
            else:
                arr = [Int(random.uniform(0, 20)) for _ in range(length)]
            test1(arr, debug&1)
        if debug & 4:
            if len(varg) > 2:
                arr = [Float(_j) for _j in varg[1:]]
            else:
                arr = [Float(random.uniform(0, 1)) for _ in range(length)]
            test1(arr, debug&1)
        if debug & 8:
            if len(varg) > 2:
                arr = [Str(_i) for _i in varg[1:]]
            else:
                arr = [Str(str(int(random.uniform(0, 99))))
                       for _ in range(length)]
            test1(arr, debug&1)

    test(sys.argv[1:])
